package com.longge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-28 01:06
 */
public class SolveNQueens {
    List<List<String>> res = new ArrayList<List<String>>();

    public List<List<String>> solveNQueens(int n) {
        String[] row = new String[n];
        Arrays.fill(row, ".");
        String[][] board = new String[n][n];
        for (int i = 0; i < n; i++) {
            board[i] = row.clone();
        }
        backtrack(board, 0);
        return res;
    }

    private void backtrack(String[][] board, int row) {
        if (row == board.length) {
            res.add(convertBoard(board));
            return;
        }
        for (int col = 0; col < board[row].length; col++) {
            if (!isVaild(board, row, col)) continue;
            board[row][col] = "Q";
            backtrack(board, row + 1);
            board[row][col] = ".";
        }


    }

    private boolean isVaild(String[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if ("Q".equals(board[i][col])) return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if ("Q".equals(board[i][j])) return false;
        }
        for (int i = row - 1, j = col -1; i >= 0 && j >=0; i--, j--) {
            if ("Q".equals(board[i][j])) return false;
        }
        return true;
    }

    private List<String> convertBoard(String[][] board) {
        List<String> res = new ArrayList<>();
        for (String[] strings : board) {
            String str = Stream.of(strings).collect(Collectors.joining());
            res.add(str);
        }
        return res;
    }

    public static void main(String[] args) {
        SolveNQueens solveNQueens = new SolveNQueens();
        solveNQueens.solveNQueens(4);
    }
}
